1. Technical Field
The present invention relates to a method and system for data processing or information handling systems in general and, in particular, to a method and system for a multiplier implementing multiplication in a computer system. Still more particularly, the present invention relates to a method and system for overlapping the process of partial product reduction when implementing multiplication in a computer system.
2. Description of the Prior Art
Applications of modern computer systems are requiring greater speed and data handling capabilities for uses such as multimedia and scientific modeling. Multimedia and scientific modeling require massive data manipulation and an extraordinary amount of high-performance arithmetic and vector-matrix operations. One such operation is the classical multiplier implementing multiplication between two bit registers. One such prior art hard-wired multiplication scheme for implementing multiplication is shown in FIG. 1. The hard-wired multiplication scheme is basically divided into two parts. The first part produces, using a multiplier 20, multiplicand 22 and a Booth encoder 24 a matrix of partial product rows 26. These partial product rows 26 are then reduced to two rows (sum and carry) 34 by some kind of counter or Wallace tree 32, shown in FIG. 1 using a 4/2 carry save adder (CSA) compressor 28 (and by way of example may use a 3/2 or 7/3 compressor). The second part reduces the two rows to one by using a big 2/1 adder 30, such as Carry Propagate Adder (CPA) or Carry-Select Adder (CSA) resulting in a final product 36. Prior art multipliers normally implement these two parts separately, and in many cases they are in separate pipeline stages. To reduce the propagation delay, one possible approach is to combine the two parts such that the final adder can start its calculation before the CSA tree finishes its tournament.
One such prior art solution for combining the two parts such that the final adder can start its calculation before the CSA tree finishes its tournament is shown in FIG. 2. As shown in FIG. 2, the addition of the lower 30 bits 38 utilizing a 16-bit carry select adder 42 are overlapped with the reduction of the partial product array 40. However, this 30-bit addition overlap does not provide a speed gain, since the left over 76 bits 44 will need the same number of logic stages 46 (8 stages) to complete the final addition as the original 106 bits do.
Therefore, there is a need for a method and system to overlap the final addition on the higher order bits as well as the lower order bits to reduce the propagation time effectively. Additionally, it would be desirable to reduce the number of left-over bits so that the final addition on these bits requires fewer logic stages to complete its process, and thus reduce the propagation delay. The subject invention herein solves these problems in a new and unique manner that has not been part of the art previously.
In view of the foregoing, it is therefore an object of the present invention to provide an improved method and system for performing multiplication utilizing a speedup multiplier in a computer system or information handling system.
It is another object of the present invention to provide an improved method and system when performing multiplication by overlapping the process of partial product reduction in a computer system or information handling system.
The foregoing objects are achieved as is now described. The method and system of the present invention overlaps the process of partial product reduction and the final adder in both higher- and lower-order bits when performing multiplication. The method and system reduces the number of left-over bits such that the final addition on these bits requires fewer logic stages to complete its process thereby reducing the propagation delay.
All objects, features, and advantages of the present invention will become apparent in the following detailed written description.